package Leetcode.DayTest;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Author: kirito
 * @Date: 2024/9/22 10:30
 * @Description:
 */

public class Test_416 {
    public static void main(String[] args) {
        Test_416 test_416 = new Test_416();
/*        int high = 4;
        int[] work = {2, 1, 1};
        System.out.println(minNumberOfSeconds(high, work));*/
        String w1 = "abcabc";
        String w2 = "abc";
        System.out.println(test_416.validSubstringCount(w1, w2));

    }

    /**
     * 给你两个字符串 word1 和 word2 。
     *
     * 如果一个字符串 x 重新排列后，word2 是重排字符串的
     * 前缀
     *  ，那么我们称字符串 x 是 合法的 。
     *
     * 请你返回 word1 中 合法
     * 子字符串
     *  的数目。
     *
     * 示例 1：
     *
     * 输入：word1 = "bcca", word2 = "abc"
     *
     * 输出：1
     *
     * 解释：
     *
     * 唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。
     *
     * 示例 2：
     *
     * 输入：word1 = "abcabc", word2 = "abc"
     *
     * 输出：10
     *
     * 解释：
     *
     * 除了长度为 1 和 2 的所有子字符串都是合法的。
     *
     * 示例 3：
     *
     * 输入：word1 = "abcabc", word2 = "aaabc"
     *
     * 输出：0
     */
    public long validSubstringCount(String word1, String word2) {
        // 创建一个数组来存储 word2 中每个字符的频率
        int[] cnt2 = new int[26]; // 假设单词只包含小写字母，所以数组长度为26
        char[] w2 = word2.toCharArray(); // 将word2转换为字符数组以便遍历
        for (char c : w2) {
            cnt2[c - 'a']++; // 更新cnt2中对应字符的频率
        }

        long ans = 0; // 用于存储合法子字符串的数量

        char[] w1 = word1.toCharArray(); // 将word1转换为字符数组以便遍历
        int n = w1.length; // word1的长度
        int l = 0; // 当前子字符串的起始索引
        int[] cnt1 = new int[26]; // 创建一个数组来存储当前子字符串中每个字符的频率
        for (int r = 0; r < n;) { // 从索引0开始遍历word1

            // 移动r直到找到一个合法的子字符串
            while (r < n && !check2(cnt1, cnt2)) {
                cnt1[w1[r] - 'a']++; // 更新cnt1中对应字符的频率
                r++; // 移动r到下一个字符
            }

            // 如果找到了一个合法的子字符串，计算其长度并累加到ans中
            if (check2(cnt1, cnt2)) {
                while (l < n && check2(cnt1, cnt2)) {
                    ans += (n - r) + 1; // 计算当前子字符串的长度并累加到ans
                    cnt1[w1[l] - 'a']--; // 更新cnt1中对应字符的频率
                    l++; // 移动l到下一个字符
                }
            }
        }
        return ans; // 返回合法子字符串的数量
    }

    public boolean check2(int[] cnt1, int[] cnt2) {

        for (int i = 0; i < 26; i++) {
            if (cnt1[i] < cnt2[i]) {
                return false;
            }
        }

        return true;
    }


    /**
     * 给你一个整数 mountainHeight 表示山的高度。
     *
     * 同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。
     *
     * 工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :
     *
     * 山的高度降低 x，需要花费 workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x 秒。例如：
     * 山的高度降低 1，需要 workerTimes[i] 秒。
     * 山的高度降低 2，需要 workerTimes[i] + workerTimes[i] * 2 秒，依此类推。
     * 返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。
     *
     * 示例 1：
     *
     * 输入： mountainHeight = 4, workerTimes = [2,1,1]
     *
     * 输出： 3
     *
     * 解释：
     *
     * 将山的高度降低到 0 的一种方式是：
     *
     * 工人 0 将高度降低 1，花费 workerTimes[0] = 2 秒。
     * 工人 1 将高度降低 2，花费 workerTimes[1] + workerTimes[1] * 2 = 3 秒。
     * 工人 2 将高度降低 1，花费 workerTimes[2] = 1 秒。
     * 因为工人同时工作，所需的最少时间为 max(2, 3, 1) = 3 秒。
     */
    public static long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        // 初始化二分查找的范围，l 设置为0，r 设置为Long.MAX_VALUE / 2
        long l = 0;
        long r = Long.MAX_VALUE / 2;

        // 使用while循环进行二分查找
        while (l + 1 < r) {
            // 计算中间值m
            long m = (l + r) / 2;
            // 如果check方法返回true，则说明在m时间内可以完成任务，因此r变为m
            if (check(workerTimes, mountainHeight, m)) {
                r = m;
            } else {
                // 如果check方法返回false，则说明在m时间内无法完成任务，因此l变为m
                l = m;
            }
        }

        // 如果check方法在l时间返回true，则返回l，否则返回r
        if (check(workerTimes, mountainHeight, l)) {
            return l;
        }
        return r;
    }

    // 辅助方法，用于检查在给定的时间x内是否可以完成任务
    //涉及到数学求解方程 https://leetcode.cn/link/?target=https%3A%2F%2Fwww.bilibili.com%2Fvideo%2FBV1WRtDejEjD%2F
    public static boolean check(int[] workerTimes, int mountainHeight, long x) {

        // 初始化总时间sum为0
        long sum = 0;
        // 遍历每个工人
        for (int w : workerTimes) {
            // 计算每个工人可以降低的高度，使用公式 t = 2 * x / w
            double t = 2.0 * x / w;
            // 计算每个工人可以降低的高度s，使用公式 s = sqrt(t)
            long s = (long) Math.sqrt(t);

            // 如果s * (s + 1) <= t，则说明这个工人可以降低s高度，否则降低s-1高度
            if (s * (s + 1) <= t) {
                sum += s;
            } else {
                sum += s - 1;
            }
        }

        // 如果sum >= mountainHeight，则说明在x时间内可以完成任务，返回true
        return sum >= mountainHeight;
    }

    public long minNumberOfSeconds_heap(int mountainHeight, int[] workerTimes) {
        //堆模拟
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        for (int t : workerTimes) {
            pq.offer(new long[]{t, t, t});
        }
        long ans = 0;
        while (mountainHeight-- > 0) {
            // 工作后总用时，当前工作（山高度降低 1）用时，workerTimes[i]
            long[] w = pq.poll();
            //nxt 下一次再降低高度的总时间  delta = time*i  base = time（一次）
            long nxt = w[0], delta = w[1], base = w[2];
            ans = nxt; // 最后一个出堆的 nxt 即为答案
            pq.offer(new long[]{nxt + delta + base, delta + base, base});
        }
        return ans;
    }



    /**
     * 给你一个字符串数组 message 和一个字符串数组 bannedWords。
     *
     * 如果数组中 至少 存在两个单词与 bannedWords 中的任一单词 完全相同，则该数组被视为 垃圾信息。
     *
     * 如果数组 message 是垃圾信息，则返回 true；否则返回 false。
     *
     * 示例 1：
     *
     * 输入： message = ["hello","world","leetcode"], bannedWords = ["world","hello"]
     *
     * 输出： true
     *
     * 解释：
     *
     * 数组 message 中的 "hello" 和 "world" 都出现在数组 bannedWords 中。
     *
     * 示例 2：
     *
     * 输入： message = ["hello","programming","fun"], bannedWords = ["world","programming","leetcode"]
     *
     * 输出： false
     *
     * 解释：
     *
     * 数组 message 中只有一个单词（"programming"）出现在数组 bannedWords 中。
     */
    public static boolean reportSpam(String[] message, String[] bannedWords) {
        Set<String> bannedWordsSet = new HashSet<>(Arrays.asList(bannedWords));

        int count = 0;
        for (String word : message) {
            if (bannedWordsSet.contains(word)) {
                count++;
                if (count >= 2) {
                    return true;
                }
            }
        }
        return false;
    }
}
